<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>План лекций</title>
  <link href=styles/styles.css rel="stylesheet" type="text/css">
</head>
<h2>Теория чисел (advanced)</h2>
<ol>
  <li>Обратные по модулю (повторение)</li>
  <ol>
    <li>Возведение в степень и Евклид. Что лучше?</li>
    <li>Умножение по модулю чисел до 10<sup>18</sup></li>
  </ol></li>
  <li>Разложение на простые множители</li>
  <ol>
    <li>Обработка k запросов за O(N<sup>1/2</sup>(1 + k/logN))</li>
    <li>Эвристика Полларда за O(N<sup>1/4</sup>logN)</li>
    <li>Квадратичное решето за o(N<sup>1/4</sup>)</li>
    <li>Поиск всех простых от 1 до N за O(N)</li>
  </ol></li>
  <li>Дискретное логарифмирование</li>
  <ol>
    <li>Постановка задачи, решение за O(N)</li>
    <li>Доказательство существования первообразной</li>
    <li>Поиск первообразной за O(N<sup>1/2</sup>)</li>
    <li>Дискретное логарифмирование за O(N<sup>1/2</sup>)</li>
    <li>Извлечение корня k-й степени из числа по модулю за O(N<sup>1/2</sup>)</li>
    <li>Извлечение корня k-й степени из числа по модулю через диксретное логарифмирование</li>
  </ol></li>
  <li>Извлечение квадратного корня</li>
  <ol>
    <li>Существование корня &minus; символ Лежандра, доказательство, проверка за O(logN)</li>
    <li>Извлечение корня для p = 4k + 3 за O(logN)</li>
    <li>Извлечение корня для p = 4k + 1 за O(logN)</li>
    <li>Переход от модуля p к модулю p<sup>k</sup></li>
    <li>Переход от модулей a, b к модулю ab (китайская теорема об остатках)</li>
  </ol></li>
</ol>
